#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/time.h>

#include <omp.h>





/*
 * Results are collected first and printed later, so that time measurements
 * do not include calls to printf().
 *
 * This uses a rather primitive data-structure without dynamic memory
 * management, but at least overflows will be detected.
 *
 * (When using multiple threads, make sure that you do not run into race
 * conditions.)
 */

struct result {
	int idx_a;
	int idx_b;
	int length;
};

#define MAX_RESULTS 1000
struct result_container {
	int current;
	int overflow;
	char *data_a;
	char *data_b;
	struct result r[MAX_RESULTS];
};


void dispatch(int sy, int sx, long size_a, long size_b, 
    char *data_a, char *data_b, int K, struct result_container *rc);


void init_result_container(struct result_container *rc, char *data_a, char *data_b)
{
	rc->current = 0;
	rc->overflow = 0;
	rc->data_a = data_a;
	rc->data_b = data_b;
}

void collect_result(struct result_container *rc, int a, int b, int len)
{
	if (rc->current >= MAX_RESULTS) {
		++rc->overflow;
		return;
	}
	rc->r[rc->current].idx_a = a;
	rc->r[rc->current].idx_b = b;
	rc->r[rc->current].length = len;

	++rc->current;
}

void print_results(struct result_container *rc, int verbose)
{
	int i, k;

	for (i = 0; i < rc->current; ++i) {
		struct result *r = &rc->r[i];

		printf("%d %d %d", r->idx_a + 1 - r->length,
					r->idx_b + 1 - r->length, r->length);
		if (verbose) {
			printf(": \"");
			for (k = 0; k < r->length; ++k) {
				printf("%c", rc->data_a[r->idx_a + 1 + k - r->length]);
			}
			printf("\"");
		}
		printf("\n");
	}
	if (rc->overflow)
		printf("Warning: %d results were lost, increase MAX_RESULTS.\n", rc->overflow);
}



int main(int argc, char **argv)
{
	int fd_a, fd_b;
	char *data_a, *data_b;
	struct stat stat_a, stat_b;
	int ret, K, verbose;
//        int nthread = 0;

	/* "Parse" arguments */
	if (argc != 4 && argc != 5 && argc != 6) {
		printf("usage: %s <file A> <file B> <K> <threads> [ -v ]\n", argv[0]);
		return 0;
	}

	/* Minimum length of matches to collect */
	K = atoi(argv[3]);

	/* Amount of output */
	verbose = argc == 6;

    /* Set number of threads */
    if ( argc >= 5 ) {
//        nthread = atoi(argv[4]);
//        printf("Number of threads: %d\n", nthread );
    }

	/* Open input files, determine their sizes, and mmap() them into memory */
	fd_a = open(argv[1], O_RDONLY);
	if (fd_a == -1) {
		perror(argv[1]);
		return 1;
	}
	fd_b = open(argv[2], O_RDONLY);
	if (fd_b == -1) {
		perror(argv[2]);
		return 1;
	}

	ret = fstat(fd_a, &stat_a);
	if (ret == -1) {
		perror("fstat A");
		return 1;
	}
	ret = fstat(fd_b, &stat_b);
	if (ret == -1) {
		perror("fstat B");
		return 1;
	}

	data_a = mmap(NULL, stat_a.st_size, PROT_READ, MAP_SHARED, fd_a, 0);
	if (data_a == MAP_FAILED) {
		perror(NULL);
		return 1;
	}
	data_b = mmap(NULL, stat_b.st_size, PROT_READ, MAP_SHARED, fd_b, 0);
	if (data_b == MAP_FAILED) {
		perror(NULL);
		return 1;
	}

	if (verbose) {
		int i;

		printf("A: \"");
		for (i = 0; i < stat_a.st_size; ++i) {
			printf("%c", data_a[i]);
		}
		printf("\"\n");

		printf("B: \"");
		for (i = 0; i < stat_b.st_size; ++i) {
			printf("%c", data_b[i]);
		}
		printf("\"\n");
	}


	/* Real work starts here */

	long size_a = stat_a.st_size;
	long size_b = stat_b.st_size;
	int i, j;

	struct result_container rc;
    struct timeval begin, end;
    
    
        init_result_container(&rc, data_a, data_b);

            gettimeofday(&begin, NULL);
        
        for ( j = 0; j < size_b; j++ )
            dispatch(0,j,size_a,size_b,data_a,data_b,K,&rc);
        for ( i = 1; i < size_a; i++ )
            dispatch(i,0,size_a,size_b,data_a,data_b,K,&rc);
        
                gettimeofday(&end, NULL);
	
                if (end.tv_usec < begin.tv_usec) {
                    end.tv_usec += 1000000;
                    begin.tv_sec += 1;
                }
                double time = (end.tv_sec - begin.tv_sec) +
                    (end.tv_usec-begin.tv_usec)/1000000.0;
                printf("time: %f\n", time);
        
            printf("\n found: \n");
            print_results(&rc, verbose);

	/* Output */
	

	/* Cleanup */

	munmap(data_a, 0);
	munmap(data_b, 0);

	close(fd_a);
	close(fd_b);

	return 0;
}

// Traverse data_a*data_b diagonally starting at sx/sy
void dispatch2(int sy, int sx, long size_a, long size_b, 
    char *data_a, char *data_b, int K, struct result_container *rc) 
{
    int i = sy, j = sx;
    int matches = 0;
    while(i < size_a && j < size_b) 
    {
        if ( data_a[i] == data_b[j] ) // We have a match...
            matches++; // ...increase the substring length counter
        else if ( matches > 0 )  // We don't have a match but have found a substring
        {
            if ( matches >= K ) // Check whether the substring is long enough
                collect_result(rc, i-1, j-1, matches); // ..and collect the result
            matches = 0; // Reset the length counter
        }
        i++; j++;
    }

    // Special case: we have traversed the diagonal but not collected the last match
    if ( matches > 0 && matches >= K )
        collect_result(rc, i, j, matches);
}

#define compare(i,j) \
        if ( data_a[i] == data_b[j] ) \
            matches++; \
        else if ( matches > 0 ) { \
            if ( matches >= K ) { \
                collect_result(rc, i-1, j-1, matches); \
            } \
            matches = 0; \
        }

void dispatch(int sy, int sx, long size_a, long size_b, 
    char *data_a, char *data_b, int K, struct result_container *rc) 
{
    int i = sy, j = sx;
    int matches = 0;
    while(i < size_a-8 && j < size_b-8) {
        compare(i,j);
        compare(i+1,j+1);
        compare(i+2,j+2);
        compare(i+3,j+3);
        compare(i+4,j+4);
        compare(i+5,j+5);
        compare(i+6,j+6);
        compare(i+7,j+7);
        i+=8; j+=8;
    }
    while ( i < size_a && j < size_b ) {
        compare(i,j);
        i++; j++;
    }
    if ( matches > 0 && matches >= K )
        collect_result(rc, i-1, j-1, matches);
}

